---
title: "火柴棒等式"
created: 2025-11-28
tags:
  - 算法
---

# 火柴棒等式

## 题目 [火柴棒等式](https://www.luogu.com.cn/problem/P1149)

给你 n 根火柴棍，你可以拼出多少个形如 A+B=C 的等式？等式中的 A、B、C 是用火柴棍拼出的整数（若该数非零，则最高位不能是 0）。用火柴棍拼数字
0\sim9 的拼法如图所示：

![[p5hsawt2-93aa5325.png]]

注意：

1. 加号与等号各自需要两根火柴棍；
2. 如果 $$$A\neq B$，则
   A+B=C 与 B+A=C 视为不同的等式$（A,B,C\geq0）$；
3. n 根火柴棍必须全部用上。

输入格式

一个整数 $n(1 \leq n\leq 24)$。

输出格式

一个整数，能拼成的不同等式的数目。

样例 #1

样例输入 #1

```text
14
```

样例输出 #1

```text
2
```

样例 #2

样例输入 #2

```text
18
```

样例输出 #2

```text
9
```

提示

【输入输出样例 1 解释】

2 个等式为 0+1=1 和 1+0=1。

【输入输出样例 2 解释】

9个等式为

$0+4=4、0+11=11、1+10=11、2+2=4、2+7=9、4+0=4、7+2=9、10+1=11、11+0=11。$

## 思路分析

![[image-8090385e.png]]

枚举每个位置能放什么 可以重复 所以是指数型枚举

枚举出来一种方案后 检查是否满足上面的两个条件 cnt++

大概率会tle的 后面再想减枝 先写着

把问题想简单了 忽略了A B C都可能是两位数的情况

但是还能过2/5……

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=30;

int plans[5],cost[10]={6,2,5,5,4,5,6,3,7,6};

int n,res;

void dfs(int u){

	if(u>3){

		int A=plans[1],B=plans[2],C=plans[3];

		if(A+B==C && cost[A]+cost[B]+cost[C]==n-4)

			res++;

		return;

	}

	for(int i=0;i<=9;i++){

		plans[u]=i;

		dfs(u+1);

		plans[u]=-1;

	}

}

int main()

{

	cin>>n;

	dfs(1);

	cout<<res;

	return 0;

}
```

要考虑每个数都可能是两位数的话 就比较复杂了

因为n≤24 也就是说刨去加号和等号后 可用的火柴数有20根

那就是意味着 A B C三个位置都可以取20根火柴可以组成的所有情况

在这20根火柴能组成的所有数里面做指数型枚举 而不是前面的0~9了

至于这20根火柴能组成的最大的合法的数是什么……头疼

假设能到1000吧 那就是说 每个位置上可以放0~1000（实际最大应该是711）

把总和也当成一个参数放进去 方便减枝

那么就变成了 三个位置 每一位都可能放0~1000 然后sum会+=calc(i)

这个calc还是比较好算的 因为不管ABC是多少位 所需要的火柴数都是每一位的需要的火柴数相加 而每一位需要的火柴数不外乎就是那几个（0~9所需要的火柴数）
所以可以按位来处理 计算出当前位需要的总火柴数

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=30;

int plans[5],cost[10010]={6,2,5,5,4,5,6,3,7,6};

int n,res;

int calc(int x){

	if(cost[x])

		return cost[x];

	else{

		int sumfire=0;

		while(x){

			sumfire+=cost[x%10];

			x/=10;

		}

		return sumfire;

	}

}

void dfs(int u,int sum){

	if(sum>n-4)

		return;

	if(u>3){

		int A=plans[1],B=plans[2],C=plans[3];

		if(A+B==C && sum==n-4)

			res++;

		return;

	}

	for(int i=0;i<=1000;i++){

		plans[u]=i;

		dfs(u+1,sum+calc(i));

		plans[u]=-1;

	}

}

int main()

{

	cin>>n;

	dfs(1,0);

	cout<<res;

	return 0;

}
```

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int path[4],cost[N]={6,2,5,5,4,5,6,3,7,6};

int n,res;

int calc(int x){

	int sum=0;

	if(cost[x])

		sum=cost[x];

	else{

		while(x){

			sum+=cost[x%10];

			x/=10;

		}

	}

	return sum;

}

void dfs(int u,int sum){

	if(sum>n)

		return;

	if(u>3){

		int A=path[1],B=path[2],C=path[3];

		if(A+B==C && sum==n)

			res++;

		return;

	}

	for(int i=0;i<=1000;i++){

		path[u]=i;

		dfs(u+1,sum+calc(i));

		path[u]=-1;

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	n-=4;

	dfs(1,0);

	cout<<res;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/DFS/指数型（每个位置都可以选所有情况）/枚举子集|枚举子集]] 🏠 [[00-刷题理模型]] ➡️ [[烤鸡|烤鸡]]